import java.math.BigInteger;

public class SequenceIsEvaluated {
    public static void main(String[] args) {
        // 只保留后四位的数就好
        int a = 1, b = 1, c = 1, d = 0;
        for(int i = 4; i <= 20190324; i++){
            d = (a+b+c)%10000;
            a = b;
            b = c;
            c = d;
        }
        System.out.println(d);
        // 数量过于庞大，使用BigInteger需要很长很长的时间
//        BigInteger first = new BigInteger("1");
//        BigInteger second = new BigInteger("1");
//        BigInteger third = new BigInteger("1");
//        for (int i = 4; i <= 20190324; i++) {
//            BigInteger cur  = first.add(second).add(third);
//            first = second;
//            second = third;
//            third = cur;
//            System.out.println(i);
//        }
//        StringBuilder str = new StringBuilder(third.toString());
//        System.out.println(str.substring(str.length() - 4, str.length()));
    }
}
